package start.demo01;

import java.lang.reflect.Array;
import java.util.Arrays;

public class T5_07_sort {
    public static void main(String[] args){
        T5_07_sort ts=new T5_07_sort();
        int[] list={2,3,2,1,2,5,7};
        sort(list,0,list.length-1);
        System.out.println(Arrays.toString(list));
    }
    public void speedSort(int[] list){//快速排序,未完成

    }
    public void speedSort(int[] list,int first,int last){//快速排序
        int mid=(first+last)/2;
        int base=list[mid];
        int low=first;
        int high=last;
        //如果先动左边，low会直接走到大于基数的位置上。low偏大，high值没操作空间
        while(low!=high) {
            while (list[low] < base && low < high)//等于基数时不会动
                low++;
            while (list[high] > base && low < high)
                high--;
            if(low<high){//交换
                int tmp=list[low];
                list[low]=list[high];
                list[high]=tmp;
            }
        }
    }
    public static void sort(int[] array, int left, int right) {
            if(left > right) {
                    return;
                 }
             // base中存放基准数
             int base = array[left];
             int i = left, j = right;
             while(i != j) {
                     // 顺序很重要，先从右边开始往左找，直到找到比base值小的数
                     while(array[j] >= base && i < j) {
                             j--;
                         }

                     // 再从左往右边找，直到找到比base值大的数
                     while(array[i] <= base && i < j) {
                             i++;
                         }

                     // 上面的循环结束表示找到了位置或者(i>=j)了，交换两个数在数组中的位置
                     if(i < j) {
                             int tmp = array[i];
                             array[i] = array[j];
                             array[j] = tmp;
                         }
                 }

             // 将基准数放到中间的位置（基准数归位）
             array[left] = array[i];
             array[i] = base;

             // 递归，继续向基准的左右两边执行和上面同样的操作
             // i的索引处为上面已确定好的基准值的位置，无需再处理
             sort(array, left, i - 1);
             sort(array, i + 1, right);
         }
}
